#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+50;

void findleft(int a[], int n, int l[]) {
    static int s[N], top;
    top = 0;
    for (int i=0; i<n; ++i) {
        while (top && a[s[top-1]] >= a[i]) {
            --top;
        }
        l[i] = top ? s[top-1] : -1;
        s[top++] = i;
    }
}

void findright(int a[], int n, int r[]) {
    static int tmp[N];
    memcpy(tmp, a, 4 * n);
    findleft(tmp, n, r);
}

void output(int a[], int n) {
    for (int i=0; i<n; ++i)
        printf("%3d%c", a[i], i==n-1? '\n':' ');
}

int main(int argc, char const *argv[])
{
    static int a[N];

    int n;
    cin >> n;
    for (int i=0; i<n; ++i)
        a[i] = rand()%n;
    output(a, n);
    // return 0;
    static int l[N], r[N];
    findleft(a, n, l);
    findright(a, n, r);
    output(l, n);
    output(r, n);
    return 0;
}